﻿#define _CRT_SECURE_NO_WARNINGS 1

//编程初学者入门训练第七十六题
//BC78 筛选法求素数
//https://www.nowcoder.com/practice/06c3dcc303654ef4926654023eca1e5a?tpId=107&tqId=33359&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D107&difficulty=undefined&judgeStatus=undefined&tags=&title=

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n = 0;
    int count = 0;
    scanf("%d", &n);
    //2~n一共有n-1个数
    //开辟数组n个空间
    int* arr = (int*)malloc((n - 1) * sizeof(int));
    if (arr == NULL) {
        perror("malloc fail\n");
        return 1;
    }

    //存储2~n之间的正整数
    for (int i = 1; i < n; i++) {
        arr[i - 1] = i + 1;
    }

    //筛选法
    for (int i = 0; i < n - 1; i++) {
        //判断arr[i]不被清零
        if (!arr[i])
            continue;

        for (int j = i + 1; j < n - 1; j++) {
            //判断arr[j]不被清零
            if (!arr[j])
                continue;

            if (arr[j] % arr[i] == 0) {
                arr[j] = 0;
                count++;
            }
        }
    }

    //输出数组
    for (int i = 0; i < n - 1; i++) {
        if (arr[i]) {
            printf("%d ", arr[i]);
        }
    }
    printf("\n");

    //输出数组中2之后被清0的个数
    printf("%d\n", count);

    return 0;
}